package 跳跃游戏;

/**
 * @author: AirMan
 * @date: 2025/4/22 14:20
 * @description:
 */
public class Solution {
    public boolean canJump(int[] nums) {
        // greedy
        // 只需要保证最大跳跃范围覆盖了重点即可！每次跳最远的距离，再覆盖范围内，寻找有没有能跳的更远的点
        // 局部最优：每次都取最远覆盖范围，在覆盖范围内，寻找能够让局部跳的更远的起跳点
        // 全局最优：每次都尽可能的覆盖的远 ==> 整体来说就跳的最远

        if (nums.length == 1){
            // 你最初位于数组的第一个下标
            return true;
        }
        int cover = nums[0];
        for (int i = 1; i < nums.length && i <= cover; i++) {
            if (i + nums[i] > cover) {
                // 每次都取最大的覆盖范围 ==> 更新覆盖范围
                cover = i + nums[i];
            }
            if (cover >= nums.length - 1) {
                // 如果覆盖到了结尾 ==> 提前结束遍历
                return true;
            }
        }
        return false;
    }
}